package com.lft.tree02.binary_tree;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;

/**
 * 二叉树
 */
public class BinaryTreeDemo2 {
	public static void main(String[] args) {
		Node node1 = new Node('A');
		Node node2 = new Node('B');
		Node node3 = new Node('C');
		Node node4 = new Node('D');
		Node node5 = new Node('E');
		Node node6 = new Node('F');
		Node node7 = new Node('G');
		Node node8 = new Node('H');
		Node node9 = new Node('I');
		
		//由于我们现在的这棵树没有规律，所以手动创建
		node1.leftChild = node2;
		node2.parentNode = node1;
		node1.rightChild = node3;
		node3.parentNode = node1;
		node2.leftChild = node4;
		node4.parentNode = node2;
		node4.leftChild = node7;
		node7.parentNode = node4;
		node4.rightChild = node8;
		node8.parentNode = node4;
		node3.leftChild = node5;
		node5.parentNode = node3;
		node3.rightChild = node6;
		node6.parentNode = node3;
		node5.rightChild = node9;
		node9.parentNode = node5;
		
		// 创建二叉树
		BinaryTree2 binaryTree = new BinaryTree2(node1);
		
		binaryTree.preOrderRecursionTraverse();
		binaryTree.preOrderTraverseByStack();
		binaryTree.infixOrderRecursionTraverse();
		binaryTree.infixOrderTraverseByStack();
		binaryTree.postOrderRecursionTraverse();
		binaryTree.postOrderTraverseByStack();
		binaryTree.levelOrderTraverse();
		
		TreeOperation.show(binaryTree.root);
		binaryTree.getMirrorByStack();
		TreeOperation.show(binaryTree.root);
		binaryTree.getMirrorByRecursion();
		TreeOperation.show(binaryTree.root);
	}
}

class BinaryTree2 {
	public Node root = null;
	
	public BinaryTree2(Node root) {
		this.root = root;
	}
	
	/**
	 * 前序遍历——递归实现
	 */
	public void preOrderRecursionTraverse() {
		System.out.println("前序遍历——递归实现：");
		preOrderRecursionTraverse(root);
		System.out.println();
	}
	
	private void preOrderRecursionTraverse(Node root) {
		if (root == null) {
			return;
		}
		root.displayNode();
		preOrderRecursionTraverse(root.leftChild);
		preOrderRecursionTraverse(root.rightChild);
	}
	
	/**
	 * 前序遍历——非递归实现
	 */
	public void preOrderTraverseByStack() {
		System.out.println("前序遍历——非递归实现：");
		preOrderTraverseByStack(root);
		System.out.println();
	}
	
	private void preOrderTraverseByStack(Node root) {
		Stack<Node> stack = new Stack<>();
		stack.push(root);
		Node cur = root;
		while (!stack.isEmpty()) {
			cur = stack.pop();
			if (cur != null) {
				cur.displayNode();
				stack.push(cur.rightChild);
				stack.push(cur.leftChild);
			}
		}
	}
	
	/**
	 * 中序遍历——递归实现
	 */
	public void infixOrderRecursionTraverse() {
		System.out.println("中序遍历——递归实现：");
		infixOrderRecursionTraverse(root);
		System.out.println();
	}
	
	private void infixOrderRecursionTraverse(Node root) {
		if (root == null) {
			return;
		}
		infixOrderRecursionTraverse(root.leftChild);
		root.displayNode();
		infixOrderRecursionTraverse(root.rightChild);
	}
	
	/**
	 * 中序遍历——非递归实现
	 */
	public void infixOrderTraverseByStack() {
		System.out.println("中序遍历——非递归实现：");
		infixOrderTraverseByStack(root);
		System.out.println();
	}
	
	private void infixOrderTraverseByStack(Node root) {
		Stack<Node> stack = new Stack<>();
		Node cur = root;
		while (cur != null || !stack.isEmpty()) {
			// 左子树入栈
			while (cur != null) {
				stack.push(cur);
				cur = cur.leftChild;
			}
			cur = stack.pop();
			// 访问根结点
			cur.displayNode();
			// 遍历右子树，将右子树入栈。
			cur = cur.rightChild;
		}
	}
	
	/**
	 * 后序遍历——递归实现
	 */
	public void postOrderRecursionTraverse() {
		System.out.println("后序遍历——递归实现：");
		postOrderRecursionTraverse(root);
		System.out.println();
	}
	
	private void postOrderRecursionTraverse(Node root) {
		if (root == null) {
			return;
		}
		postOrderRecursionTraverse(root.leftChild);
		postOrderRecursionTraverse(root.rightChild);
		root.displayNode();
	}
	
	/**
	 * 后序遍历——非递归实现
	 */
	public void postOrderTraverseByStack() {
		System.out.println("后序遍历——非递归实现：");
		postOrderTraverseByStack(root);
		System.out.println();
	}
	
	private void postOrderTraverseByStack(Node root) {
		Stack<Node> stack = new Stack<>();
		Node cur = root;
		// 前一个已经访问过的节点
		Node last = null;
		while (cur != null || !stack.isEmpty()) {
			while (cur != null) {
				stack.push(cur);
				cur = cur.leftChild;
			}
			cur = stack.peek();
			// 当前节点的右子树为空，或者已经被访问，由访问当前节点
			if (cur.rightChild == null || cur.rightChild == last) {
				cur.displayNode();
				last = cur;
				stack.pop();
				cur = null;
			} else {
				// 否则访问右子树。
				cur = cur.rightChild;
			}
		}
	}
	
	/**
	 * 层序遍历——使用队列
	 */
	public void levelOrderTraverse() {
		System.out.println("层序遍历：");
		levelOrderTraverse(root);
		System.out.println();
	}
	
	private void levelOrderTraverse(Node root) {
		Queue<Node> queue = new ArrayDeque<>();
		Node cur = root;
		while (cur != null || !queue.isEmpty()) {
			while (cur != null) {
				// 第一次需要放入根节点。
				if (queue.isEmpty()) {
					queue.add(cur);
				}
				// 放左子节点。
				if (cur.leftChild != null) {
					queue.add(cur.leftChild);
				}
				if (cur.rightChild != null) {
					queue.add(cur.rightChild);
				}
				// 每一个节点和它的左右子节点添加完成后。跳出循环。
				cur = null;
			}
			cur = queue.poll();
			cur.displayNode();
			cur = queue.peek();
		}
	}
	
	/**
	 * 判断树是否为空
	 * @return
	 */
	public boolean isEmpty() {
		return root == null;
	}
	
	/**
	 * 获取树的深度。
	 * @return
	 */
	public int getDeepth() {
		return getDeepth(root);
	}
	
	private int getDeepth(Node root) {
		return root == null ? 0 : Math.max(getDeepth(root.leftChild), getDeepth(root.rightChild)) + 1;
	}
	
	/**
	 * 获取树的节点数
	 * @return
	 */
	public int size() {
		return size(root);
	}
	
	private int size(Node root) {
		if (root == null) {
			return 0;
		}
		return size(root.leftChild) + size(root.rightChild) + 1;
	}
	
	/**
	 * 获取叶子节点的个数。
	 * @return
	 */
	public int numberOfLeaves() {
		return numberOfLeaves(root);
	}
	
	private int numberOfLeaves(Node root) {
		// 节点为空，返回 0
		if (root == null) {
			return 0;
		}
		// 没有左右子节点，返回1.当前节点就是叶子节点。
		if (root.leftChild == null && root.rightChild == null) {
			return 1;
		}
		return numberOfLeaves(root.leftChild) + numberOfLeaves(root.rightChild);
	}
	
	/**
	 * 获得满节点（度为2）的个数。
	 * @return
	 */
	public int numberOfFulls1() {
		return numberOfFulls(root);
	}
	
	/**
	 * 根据性质 3 可以得出
	 * 性质 3：对任何一棵二叉树 T，如果其叶子节点数为 n0，度为 2 的结点数为 n2，则n0 = n2 + 1。
	 * @return
	 */
	public int numberOfFulls2() {
		return this.numberOfLeaves(root) - 1;
	}
	
	private int numberOfFulls(Node root) {
		if (root == null) {
			return 0;
		} else if (root.leftChild == null && root.rightChild == null) {
			// 当前节点没有左右子节点，当前节点就是一个叶子节点，不是满节点，直接返回0
			return 0;
		} else if (root.leftChild != null && root.rightChild == null) {
			// 左子树不为空，右子树为空，递归左子树查找满节点。
			return numberOfFulls(root.leftChild);
		} else if (root.leftChild == null && root.rightChild != null) {
			// 右子树不为空，左子树为空，递归右子树查找满节点。
			return numberOfFulls(root.rightChild);
		} else {
			// 左右子树都不为空，当前节点也是满节点，再递归左右子树。
			return 1 + numberOfFulls(root.leftChild) + numberOfFulls(root.rightChild);
		}
	}
	
	/**
	 * 查找指定值的节点
	 * @param value
	 * @return
	 */
	public Node findValue(int value) {
		return findValue(root, value);
	}
	
	private Node findValue(Node node, int value) {
		//根节点为空，直接返回空。
		if (node == null) {
			return null;
		}
		// 根节点不为空，根节点的值跟查询的值一样。直接返回根节点。
		else if (node != null && node.data == value) {
			return node;
		} else {
			// 先从左子树中查找。
			Node nodeL = findValue(node.leftChild, value);
			// 再从右子树中查找。
			Node nodeR = findValue(node.rightChild, value);
			// 左子树中找到的值非空，且跟要查找的值相等，返回该节点。
			if (nodeL != null && nodeL.data == value) {
				return nodeL;
			}
			// 右子树中找到的值非空，且跟要查找的值相等，返回该节点。
			else if (nodeR != null && nodeR.data == value) {
				return nodeR;
			} else {
				// 否则就是没找到。返回空。
				return null;
			}
		}
	}
	
	/**
	 * 镜像二叉树——递归实现
	 */
	public void getMirrorByRecursion() {
		getMirrorsByRecursion(root);
	}
	
	private void getMirrorsByRecursion(Node node) {
		if (node == null) {
			return;
		}
		Node temp = node.leftChild;
		node.leftChild = node.rightChild;
		node.rightChild = temp;
		if (node.leftChild != null) {
			// 递归以左子节点为根节点，翻转左子树。
			getMirrorsByRecursion(node.leftChild);
		}
		if (node.rightChild != null) {
			// 递归以右子节点为根节点，翻转右子树。
			getMirrorsByRecursion(node.rightChild);
		}
	}
	
	/**
	 * 镜像二叉树——非递归实现
	 * 按照先序遍历二叉树的顺序，每遇到一个节点，判断当前节点是否有孩子，如果有孩子，我们交换其左右孩子，然后把非空孩子入栈。直到栈为空。
	 */
	public void getMirrorByStack() {
		getMirrorByStack(root);
	}
	
	private void getMirrorByStack(Node node) {
		Stack<Node> stack = new Stack<>();
		stack.push(node);
		while (!stack.isEmpty()) {
			Node top = stack.pop();
			Node temp = top.leftChild;
			top.leftChild = top.rightChild;
			top.rightChild = temp;
			if (top.leftChild != null) {
				stack.push(top.leftChild);
			}
			if (top.rightChild != null) {
				stack.push(top.rightChild);
			}
		}
	}
}

class Node {
	/**
	 * 数据域
	 */
	public int data;
	/**
	 * 左子节点
	 */
	public Node leftChild;
	/**
	 * 右子节点
	 */
	public Node rightChild;
	/**
	 * 父节点，为了便于删除。
	 */
	public Node parentNode;
	
	public Node(int data) {
		this.data = data;
	}
	
	public void displayNode() {
		System.out.print(data + " ");
	}
}